
//六、红黑树的删除
//------------------------------------------------------------
//红黑树的删除结点
rb_node_t* rb_erase(key_t key, rb_node_t *root)
{
    rb_node_t *child, *parent, *old, *left, *node;
    color_t color;
 
    if (!(node = rb_search_auxiliary(key, root, NULL))) {
    //调用rb_search_auxiliary查找要删除的结点
        printf("key %d is not exist!/n");
        return root;
    }
 
    old = node;
 
    if (node->left && node->right) {
        node = node->right;
        while ((left = node->left) != NULL) {
            node = left;
        }
        child = node->right;
        parent = node->parent;
        color = node->color;
  
        if (child) {
            child->parent = parent;
        }
        if (parent) {
            if (parent->left == node) {
                parent->left = child;
            } else {
                parent->right = child;
            }
        } else {
            root = child;
        }
  
        if (node->parent == old) {
            parent = node;
        }
  
        node->parent = old->parent;
        node->color = old->color;
        node->right = old->right;
        node->left = old->left;
  
        if (old->parent)
        {
            if (old->parent->left == old)
            {
                old->parent->left = node;
            }
            else
            {
                old->parent->right = node;
            }
        } 
        else
        {
            root = node;
        }
  
        old->left->parent = node;
        if (old->right)
        {
            old->right->parent = node;
        }
    } else {
        if (!node->left)
        {
            child = node->right;
        }
        else if (!node->right)
        {
            child = node->left;
        }
        parent = node->parent;
        color = node->color;
  
        if (child)
        {
            child->parent = parent;
        }
        if (parent)
        {
            if (parent->left == node)
            {
                parent->left = child;
            }
            else
            {
                parent->right = child;
            }
        }
        else
        {
            root = child;
        }
    }
 
    free(old);
 
    if (color == BLACK)
    {
        root = rb_erase_rebalance(child, parent, root); //调用rb_erase_rebalance来恢复红黑树性质
    }
 
    return root;
}
 
 
//七、红黑树的4种删除情况
//----------------------------------------------------------------
//红黑树修复删除的4种情况
//为了表示下述注释的方便，也为了让下述代码与我的倆篇文章相对应，
//x表示要删除的结点，*other、w表示兄弟结点，
//----------------------------------------------------------------
static rb_node_t* rb_erase_rebalance(rb_node_t *node, rb_node_t *parent, rb_node_t *root)
{
    rb_node_t *other, *o_left, *o_right;   //x的兄弟*other，兄弟左孩子*o_left,*o_right
 
    while ((!node || node->color == BLACK) && node != root) 
    {
        if (parent->left == node)
        {
            other = parent->right;
            if (other->color == RED)   //情况1：x的兄弟w是红色的
            {
                other->color = BLACK;  
                parent->color = RED;   //上俩行，改变颜色，w->黑、p[x]->红。
                root = rb_rotate_left(parent, root);  //再对p[x]做一次左旋
                other = parent->right;  //x的新兄弟new w 是旋转之前w的某个孩子。其实就是左旋后的效果。
            }
            if ((!other->left || other->left->color == BLACK) &&
                (!other->right || other->right->color == BLACK))  
                          //情况2：x的兄弟w是黑色，且w的俩个孩子也都是黑色的
 
            {                         //由于w和w的俩个孩子都是黑色的，则在x和w上得去掉一黑色，
                other->color = RED;   //于是，兄弟w变为红色。
                node = parent;    //p[x]为新结点x
                parent = node->parent;  //x<-p[x]
            }
            else                       //情况3：x的兄弟w是黑色的，
            {                          //且，w的左孩子是红色，右孩子为黑色。
                if (!other->right || other->right->color == BLACK)
                {
                    if ((o_left = other->left))   //w和其左孩子left[w]，颜色交换。
                    {
                        o_left->color = BLACK;    //w的左孩子变为由黑->红色
                    } 
                    other->color = RED;           //w由黑->红
                    root = rb_rotate_right(other, root);  //再对w进行右旋，从而红黑性质恢复。
                    other = parent->right;        //变化后的，父结点的右孩子，作为新的兄弟结点w。
                }
                            //情况4：x的兄弟w是黑色的
    
                other->color = parent->color;  //把兄弟节点染成当前节点父节点的颜色。
                parent->color = BLACK;  //把当前节点父节点染成黑色
                if (other->right)      //且w的右孩子是红
                {
                    other->right->color = BLACK;  //兄弟节点w右孩子染成黑色
                }
                root = rb_rotate_left(parent, root);  //并再做一次左旋
                node = root;   //并把x置为根。
                break;
            }
        }
        //下述情况与上述情况，原理一致。分析略。
        else
        {
            other = parent->left;
            if (other->color == RED)
            {
                other->color = BLACK;
                parent->color = RED;
                root = rb_rotate_right(parent, root);
                other = parent->left;
            }
            if ((!other->left || other->left->color == BLACK) &&
                (!other->right || other->right->color == BLACK))
            {
                other->color = RED;
                node = parent;
                parent = node->parent;
            }
            else
            {
                if (!other->left || other->left->color == BLACK)
                {
                    if ((o_right = other->right))
                    {
                        o_right->color = BLACK;
                    }
                    other->color = RED;
                    root = rb_rotate_left(other, root);
                    other = parent->left;
                }
                other->color = parent->color;
                parent->color = BLACK;
                if (other->left)
                {
                    other->left->color = BLACK;
                }
                root = rb_rotate_right(parent, root);
                node = root;
                break;
            }
        }
    }
 
    if (node)
    {
        node->color = BLACK;  //最后将node[上述步骤置为了根结点]，改为黑色。
    }  
    return root;  //返回root
}